'''
https://leetcode.cn/problems/min-cost-to-connect-all-points/description
'''
from typing import List

class UF:
    def __init__(self, n) -> None:
        self.father = [i for i in range(n)]
    def find(self, x):
        if x == self.father[x]: return x
        self.father[x] = self.find(self.father[x])
        return self.father[x]
    def union(self, x, y):
        fx, fy = self.find(x), self.find(y)
        if fx == fy: return False
        self.father[fy] = fx
        return True

class Solution:
    def minCostConnectPoints(self, points: List[List[int]]) -> int:
        path = []
        n = len(points)
        for i in range(n):
            p = points[i]
            for j in range(i + 1, n):
                q = points[j]
                manhattan = abs(p[0] - q[0]) + abs(p[1] - q[1])
                path.append((i, j, manhattan))

        path.sort(key=lambda x: x[2])
        uf = UF(n)
        n_edges = 0
        total_cost = 0
        for u, v, cost in path:
            if uf.union(u, v):
                total_cost += cost
                n_edges += 1
            if n_edges == n-1:
                return total_cost
        return total_cost if n_edges == n-1 else -1


